package com.zyk.grate_offer.class02;

/**
 * 现有司机N*2人，调度中心会将所有司机平分给A、B两个区域
 * 第 i 个司机去A可得收入为income[i][0]，
 * 第 i 个司机去B可得收入为income[i][1]，
 * 返回所有调度方案中能使所有司机总收入最高的方案，是多少钱
 *
 * @author zhangsan
 * @date 2021/4/23 13:11
 */
public class Code04_Driver {

    // 暴力解
    public static int bestPlan1(int[][] income) {
        int N = income.length;
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = i;
        }
        return process1(arr, 0, income);
    }

    public static int process1(int[] arr, int index, int[][] matrix) {
        int money = 0;
        if (index == arr.length) {
            for (int i = 0; i < arr.length; i++) {
                money += i < (arr.length / 2) ? matrix[arr[i]][0] : matrix[arr[i]][1];
            }
        } else {
            for (int i = index; i < arr.length; i++) {
                swap(arr, index, i);
                money = Math.max(money, process1(arr, index + 1, matrix));
                swap(arr, index, i);
            }
        }
        return money;
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // 2, 暴力尝试, 有优化: 只要没有剩余的就全分配给B. 或全分配给A
    public static int bestPlan2(int[][] income) {
        if (income == null || (income.length & 1) == 1) return 0;
        int A = income.length / 2;
        return process2(income, 0, A);
    }

    public static int process2(int[][] income, int i, int rest) {
        if (i == income.length) return 0;
        if (i >= income.length - rest) {     // B分完了, 全去A
            return process2(income, i + 1, rest - 1) + income[i][0];
        }
        if (rest == 0) { // A分完了, 全去B
            return process2(income, i + 1, rest) + income[i][1];
        }
        return Math.max(process2(income, i + 1, rest - 1) + income[i][0], process2(income, i + 1, rest) + income[i][1]);
    }

    // 改dp
    public static int bestPlan3(int[][] income) {
        if (income == null || (income.length & 1) == 1) return 0;
        int R = income.length, C = R >> 1;
        int[][] dp = new int[R + 1][C + 1];
        // r: i     c: rest
        //先填第一列(即rest == 0),    然后从左往右(外层) 从下往上填
        for (int r = R - 1; r >= 0; r--) {
            dp[r][0] = dp[r + 1][0] + income[r][1];
        }
        for (int c = 1; c <= C; c++) {
            for (int r = R - 1; r >= 0; r--) {
                if (r >= R - c) {     // B分完了, 全去A
                    dp[r][c] = dp[r + 1][c - 1] + income[r][0];
                }else {
                    dp[r][c] = Math.max(dp[r + 1][c - 1] + income[r][0], dp[r + 1][c] + income[r][1]);
                }
            }
        }
        return dp[0][C];
    }


    // 返回随机len*2大小的正数矩阵
    // 值在0~value-1之间
    public static int[][] randomMatrix(int len, int value) {
        int[][] ans = new int[len << 1][2];
        for (int i = 0; i < ans.length; i++) {
            ans[i][0] = (int) (Math.random() * value);
            ans[i][1] = (int) (Math.random() * value);
        }
        return ans;
    }

    public static void main(String[] args) {
        /*int[][] matrix = {
                {12,15},
                {24,15},
                {23,26},
                {12,18},
                {14,15},
                {28,16},
                {16,14},
                {16,15},
        };
        System.out.println(bestPlan1(matrix));
        System.out.println(bestPlan2(matrix));
        System.out.println(bestPlan3(matrix));*/
        int N = 5;
        int value = 100;
        int testTime = 500;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int len = (int) (Math.random() * N) + 1;
            int[][] matrix = randomMatrix(len, value);
            int ans1 = bestPlan1(matrix);
            int ans2 = bestPlan2(matrix);
            int ans3 = bestPlan3(matrix);
            if (ans1 != ans2 || ans1 != ans3) {
                System.out.println(ans1);
                System.out.println(ans2);
                System.out.println(ans3);
                System.out.println("Oops!");
            }
            /*if (ans1 != ans2) {
                System.out.println("OOPS");
                break;
            }*/
        }
        System.out.println("测试结束");
    }

}
